import java.util.Arrays;
import java.util.HashMap;
import java.util.Hashtable;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-26
 * Time: 20:28
 */

/**
 * 用来产生不同的哈希函数
 */
class SimpleHash{
    public int capacity;  // 当前容量, 指的就是 能存储的数字的个数, 即 bit 位数
    public int seed;  // 随机种子
    public SimpleHash(int capacity,int seed){
        this.capacity=capacity;
        this.seed=seed;
    }

    // 借用源码的 hash 函数然后修改一下, 产生不同的哈希函数
    public int hash(String key) {
        int h;
        // 源码中是 (n - 1) & hash
        // 这里我们用 (seed*(capacity-1))& hash
        // 其中 hash = hash ^ ( hash>>>16 )
        return (key == null) ? 0 : (seed*(capacity-1))&((h = key.hashCode()) ^ (h >>> 16));
    }
}

/**
 * 布隆过滤器, 原理就是 通过不同的哈希函数, 将同一个元素, 存到不同的位置
 * 想要查询这个元素在不在时, 就是同时看这几个位置是不是同时为 1 ,
 * 是则可能存在, 否则一定不存在
 */
public class MyBloomFilter {
    public static final int DEFAULT_SIZE=1<<20;

    public int[] seeds={13,5,9,4,1,7}; //　产生不同的哈希函数的种子
    SimpleHash[] simpleHashes; // 存放不同的哈希函数
//    位图, 用来存储 数据是否存在
    public MyBitSet myBitSet;

    public MyBloomFilter(){
        this.myBitSet=new MyBitSet(DEFAULT_SIZE);
        this.simpleHashes=new SimpleHash[seeds.length];
//        产生了 6 个不同的哈希函数
//        实际的 哈希函数的个数 与 多个因素有关
        for (int i = 0; i < seeds.length; i++) {
            simpleHashes[i]=new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    /**
     * 添加元素到 布隆过滤器
     * @param value
     */
    public void add(String value){
        for (SimpleHash simpleHash:simpleHashes) {
            int hashCode=simpleHash.hash(value);
            myBitSet.set(hashCode);
        }
    }

    /**
     * 判断这个元素是否存在
     * @param value
     * @return
     */
    public boolean contains(String value){
        for (SimpleHash simpleHash:simpleHashes) {
            int hashCode=simpleHash.hash(value);
            boolean flag=myBitSet.get(hashCode);
//            如果其中一个位置为  0 , 说明这个元素一定不存在
            if(!flag){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        myBloomFilter.add("hello");
        myBloomFilter.add("hello2");
        myBloomFilter.add("bit");
        myBloomFilter.add("haha");

        System.out.println(myBloomFilter.contains("hello"));
        System.out.println(myBloomFilter.contains("hell"));
        System.out.println(myBloomFilter.contains("haha"));
    }
}
